package lc.q250_300;

import lc.q1_50.Q29;

/**
 * nim游戏
 *
 * 你和你的朋友，两个人一起玩 Nim 游戏：
 *
 * 桌子上有一堆石头。
 * 你们轮流进行自己的回合， 你作为先手 。
 * 每一回合，轮到的人拿掉 1 - 3 块石头。
 * 拿掉最后一块石头的人就是获胜者。
 * 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
 */
public class Q292 {
    public boolean canWinNim(int n) {
        // 只要石头不是4的倍数，就有机会赢，并且只要把剩余n变成4的倍数，让对方输
        // 看最后一回合，如果剩余4，那显然你输了
        // 而继续，如果剩余8，那你无论怎么拿，对手都可以让剩余结果是4，你也输了
        // 依次类推
        return n % 4 != 0;
//        if (n <= 0) {
//            return false;
//        }
//        if (n <= 3) {
//            return true;
//        }
        // 分别拿1个2个3个判断能否赢,对方如果输掉，则我们赢，但是对手可能也取最优解
//        return !canWinNim(n - 1) || !canWinNim(n - 2) || !canWinNim(n - 3);
    }

    public static void main(String[] args) {
        Q292 q292 = new Q292();
        System.out.println(q292.canWinNim(8));
    }
}
